#include "DoubleLinkList.h"
#include "DynamicArray.h"
#include <iostream>
#include <stddef.h>

// 改为void *

DoubleLinkList::DoubleLinkList() : size(0)
{
    head = tail = new Node(0);
    Free = nullptr;
    Print = nullptr;
    Compr = nullptr;
    AllCompr = nullptr;
}

// 拷贝构造
DoubleLinkList::DoubleLinkList(const DoubleLinkList &list)
{
    size = list.size;
    // 复制大小
    head = tail = new Node(0);
    Node *tp = head;
    Node *travelPoint = list.head->next;
    while (travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        tp->next = newNode;
        newNode->prev = tp;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    tail = tp;
}

DoubleLinkList &DoubleLinkList::operator=(const DoubleLinkList &list)
{
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 下一个节点存下来
        if (Free != nullptr)
            Free(head->value);
        delete head;
        head = nextNode; // 接着指向下一个
    }
    tail = nullptr;

    size = list.size;
    // 复制大小
    head = tail = new Node(0); // 伪头节点 尾节点  申请同一块内存
    Node *tp = head;
    Node *travelPoint = list.head->next;
    while (travelPoint != nullptr)
    {
        Node *newNode = new Node(travelPoint->value);
        tp->next = newNode;
        newNode->prev = tp;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    tail = tp;
    return *this;
}

DoubleLinkList::~DoubleLinkList()
{
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 下一个节点存下来
        if (Free != nullptr)
            // Free(nextNode->value);
            Free(head->value);
        delete head;
        head = nextNode; // 接着指向下一个
    }
    tail = nullptr;
}

// 尾插
void DoubleLinkList::InsertTail(const ElementType &element) // O(1)
{
    Node *newNode = new Node(element);
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    size++;
}

void DoubleLinkList::InsertByIndex(size_t index, const ElementType &element)
{
    if (index > size) // 杜绝尾插，否则可能会没有newNode->next,指向空
    {
        std::cout << "位置非法！\n";
        return;
    }
    Node *travePoint = head;
    for (size_t i = 0; i < index; i++)
    {
        travePoint = travePoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travePoint->next;
    newNode->prev = travePoint;

    travePoint->next = newNode;
    if (size != 0)
        newNode->next->prev = newNode;
    size++;
}

void DoubleLinkList::RemoveByIndex(size_t index)
{
    if (index >= size)
    {
        std::cout << "位置非法" << std::endl;
        return;
    }
    Node *travelPoint = head;
    for (size_t i = 0; i < index; i++)
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    if (freeNode->next != nullptr)
        travelPoint->next->prev = travelPoint;
    if (freeNode->next == nullptr)
        tail = tail->prev;
    delete freeNode;
    size--;
}

void DoubleLinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if (Compr(travelPoint->next->value, element))
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            travelPoint->next->prev = travelPoint;
            if (freeNode->next != nullptr)
                travelPoint->next->prev = travelPoint;
            if (freeNode->next == nullptr)
                tail = tail->prev;
            delete freeNode;
            size--;
        }
        else
        {
            travelPoint = travelPoint->next;
        }
    }
}

ElementType *DoubleLinkList::FindByIndex(size_t index)
{
    if (index >= size)
    {
        return nullptr;
    }
    Node *travePoint = head->next;
    for (size_t i = 0; i < index; i++)
    {
        travePoint = travePoint->next; // 停在了index
    }
    return &travePoint->value;
}

DARRAY::DynamicArray DoubleLinkList::FindByElement(const ElementType &element)
{
    DARRAY::DynamicArray array;
    Node *travePoint = head->next;
    while (travePoint != nullptr)
    {
        if (Compr(travePoint->value, element))
        {
            array.InsertTail(&travePoint->value);
        }
        travePoint = travePoint->next;
    }
    return array;
}

void DoubleLinkList::UpdateByIndex(size_t index, const ElementType &element)
{
    if (index >= size)
    {
        std::cout << "位置非法!\n";
        return;
    }
    Node *travePoint = head->next;
    for (size_t i = 0; i < index; i++)
    {
        travePoint = travePoint->next;
    }
    travePoint->value = element;
}

void DoubleLinkList::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    Node *travePoint = head->next;
    int flag = 0;
    while (travePoint != nullptr)
    {
        if (Compr(travePoint->value, oldValue))
        {
            travePoint->value = newValue;
            flag = 1;
        }
        travePoint = travePoint->next;
    }
    if (flag == 0)
    {
        std::cout << "没有" << std::endl;
    }
}

void DoubleLinkList::BubbleSort()
{
    for (size_t i = 0; i < size - 1; i++)
    {
        Node *travePoint = head; // 每次循环都回到链表的开头
        for (size_t j = 0; j < size - i - 1; j++)
        {
            if (Compr(travePoint->next->value, travePoint->next->next->value) > 0)
            {
                Node *front = travePoint->next;
                Node *back = front->next;
                if (back->next != nullptr)
                {
                    front->next = back->next;
                    back->next->prev = front;
                }
                else
                {
                    front->next = back->next = nullptr;
                    tail = front;
                }
                back->prev = travePoint;
                back->next = front;
                front->prev = back;

                travePoint->next = back;
            }
            travePoint = travePoint->next;
        }
    }
}

// void DoubleLinkList::BubbleSort()
// {
//     for (size_t i = 0; i < size - 1; i++)
//     {
//         Node *travePoint = head->next;
//         for (size_t j = 0; j < size - 1 - i; j++)
//         {
//             if (Compr(travePoint->next->value, travePoint->next->next->value) > 0)
//             {
//             }
//         }
//     }
// }

void DoubleLinkList::Sort()
{
    FastSort(head->next, nullptr);
}

void DoubleLinkList::show()
{
    std::cout << "size: " << size << std::endl;
    Node *travelPoint = head->next; // 从头指针的下一个
    while (travelPoint != nullptr)  // 链表还未结束
    {
        Print(travelPoint->value);
        // std::cout << travelPoint->value << " ";
        travelPoint = travelPoint->next; // 遍历指针向后走
    }
    std::cout << std::endl;

    travelPoint = tail;
    while (travelPoint != head)
    {
        Print(travelPoint->value);
        // std::cout << travelPoint->value << " ";
        travelPoint = travelPoint->prev;
    }
    std::cout << std::endl;
}

void DoubleLinkList::FastSort(Node *start, Node *end)
{
    // 终止条件
    if (start == end)
        return;
    Node *temp = start;       // 基准值指针
    Node *slow = start;       // 慢指针
    Node *fast = start->next; // 快指针
    while (fast != end)       // 快指针没有到结尾
    {
        // 快指针指向的值比基准值小
        if (fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(slow->value, fast->value); // 交换快慢指针的值
        }
        fast = fast->next;
    }
    std::swap(temp->value, slow->value); // 将基准值归位
    FastSort(start, slow);               // [start,slow)
    FastSort(slow->next, end);
}
